package class_3;

import java.util.Arrays;
import java.util.Random;

//最低票价
//在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
//在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
//每一项是一个从 1 到 365 的整数
//火车票有 三种不同的销售方式
//一张 为期1天 的通行证售价为 costs[0] 美元
//一张 为期7天 的通行证售价为 costs[1] 美元
//一张 为期30天 的通行证售价为 costs[2] 美元
//通行证允许数天无限制的旅行
//例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
//那么我们可以连着旅行 7 天(第2~8天)
//返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
//测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/  力扣
/**
 * 一维动态规划:最低票价
 */
public class Coding_mincostTickets {
	public static int[] duringations = {1,7,30};
	public static int mincostTickets(int[] days, int[] costs) {
		return f(days, costs, 0);//辅助方法
	}
	/**
	 * 从第days[i]天出发需要花费多少天？
	 * @param days
	 * @param costs
	 * @param cur
	 * @return
	 */
	public static int f(int[] days, int[] costs, int cur) {
		if(cur==days.length) {
			return 0;
		}
		int ans = Integer.MAX_VALUE;//假定系统最大值
		//遍历三种票价的结果， 筛出最小值。
		for(int i=0, j = cur;i<3;i++) {
			while(j<days.length && days[cur] + duringations[i] > days[j]) {
				j++;//求解当前不越界的新出发点
			}
			//第一种方案与第二种方案进行比较， 比较结果在和第三种比较。
			ans = Math.min(ans, costs[i] + f(days,costs,j));
		}
		return ans;
	}
	
	/**
	 * 自顶向上的最优解
	 * 记忆化搜索
	 */
	public static int mincostTickets2(int[] days, int[] costs) {
		int[] dp = new int[days.length];
		Arrays.fill(dp, Integer.MAX_VALUE);//开局一张表
		return f1(days, costs, 0, dp);//辅助方法
	}
	public static int f1(int[] days, int[] costs, int cur, int[] dp) {
		if(cur==days.length) {
			return 0;
		}
		if(dp[cur]!=-1) {
			return dp[cur];
		}
		int ans = Integer.MAX_VALUE;
		//遍历三种票价的结果， 筛出最小值。
		for(int i=0, j = cur;i<3;i++) {
			while(j<days.length && days[cur] + duringations[i] > days[j]) {
				j++;//求解当前不越界的新出发点
			}
			//第一种方案与第二种方案进行比较， 比较结果在和第三种比较。
		ans = Math.min(ans, costs[i] + f1(days,costs,j, dp));
		}
		dp[cur]=ans;
		return ans;
	}
	/**
	 * 会不会重复调用， 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] days = new int[30];
		int[] costs = new int[3];
		Random random = new Random();
		/**
		 * 利用随机数和排序生成符合题目条件的测试样例。---对数器
		 */
		for(int i=0;i<days.length;i++) {
			days[i] = random.nextInt(1,366);
		}
		Arrays.sort(days);
		for(int i=0;i<costs.length;i++) {
			costs[i] = random.nextInt(1,1001);
		}
		Arrays.sort(costs);
		System.out.println("days:"+ Arrays.toString(days));
		System.out.println("costs:" + Arrays.toString(costs));
		long startTime = System.nanoTime();
		int ret = mincostTickets(days, costs);
		long endTime = System.nanoTime();
		System.out.println("最低票价:"+ ret);
		System.out.println("暴力递归共耗时"+ (endTime - startTime) + " 纳秒 =="+(endTime - startTime)*1.0/Math.pow(10, 9)+"秒");
		
		
		startTime = System.nanoTime();
		ret = mincostTickets2(days, costs);
		endTime = System.nanoTime();
		System.out.println("最低票价:"+ ret);
		System.out.println("自顶向上动态规划共耗时"+ (endTime - startTime) + " 纳秒 ");
		
	}
}
